package cn.rocky.structures.array_list;

import java.util.Arrays;

/**
 * 数组:
 * 1.数组是相同数据类型的元素集合（int 不能存放 double）
 * 2.数组中各元素的存储是有先后顺序的，它们在内存中按照这个顺序连续存放到一起。内存地址连续。
 * 3.数组获取元素的时间复杂度为O(1)
 * HashMap的拉链寻址结构,ThreadLocal的开放寻址结构都是从一维数组实现。
 */
public class ArrayList<E> implements List<E>{

    /**
     * 默认初始空间
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空元素
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList 元素数组缓存区
     */
    transient Object[] elementData;

    /**
     * List 集合元素数量
     */
    private int size;

    public ArrayList() {
        // 初始化 ArrayList阶段,如果不指定大小,默认会初始化一个空的元素。这个时候是没有默认长度的。
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    @Override
    public boolean add(E e) {
        // 确保内部容量
        int minCapacity = size + 1;
        // 那么什么时候给初始化的长度呢？
        // 是在首次添加元素的时候，因为所有的添加元素操作，也都是需要判断容量，
        // 以及是否扩容的。那么在 add 添加元素时统一完成这个事情，还是比较好处理的。
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
        }
        // 判断扩容操作
        if (minCapacity - elementData.length > 0) {
            int oldCapacity = elementData.length;
            // 1010 + 1010>>1(0101) --> 15 右移1位1.5倍扩容
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            // 之后就是随着元素的添加，容量是会不足的。
            // 当容量不足的是，需要进行扩容操作。同时还得需要把旧数据迁移到新的数组上。
            // 所以数据的迁移算是一个比较耗时的操作
            // Arrays.copyOf 实际上是创建一个新的空间数组，之后调用的 System.arraycopy 迁移到新创建的数组上。
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        // 添加元素
        elementData[size++] = e;
        return true;
    }

    @Override
    public E remove(int index) {
        E oldValue = (E)elementData[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            // System.arraycopy是一个本地方法,可以让你从原数组的特定位置，迁移到新数组的指定位置和迁移数量。
            // 从原始数组的某个位置，拷贝到目标对象的某个位置开始后n个元素
            System.arraycopy(elementData,index + 1, elementData,index, numMoved);
        }
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }

    @Override
    public E get(int index) {
        return (E) elementData[index];
    }

    @Override
    public String toString() {
        return "ArrayList{" +
                "elementData=" + Arrays.toString(elementData) +
                ", size=" + size +
                '}';
    }
}

/**
 * 常见面试题
 * 1.数据结构中有哪些是线性表数据结构？
 * 2.数组的元素删除和获取，时间复杂度是多少？
 * 3.ArrayList 中默认的初始化长度是多少？
 * 4.ArrayList 中扩容的范围是多大一次？
 * 5.ArrayList 是如何完成扩容的，System.arraycopy 各个入参的作用是什么？
 */
